// 辅助函数：经纬度点插值
function interpolate(p1, p2, t) {
  return {
    lon: p1.lon + (p2.lon - p1.lon) * t,
    lat: p1.lat + (p2.lat - p1.lat) * t,
  };
}

// Edge类
class Edge {
  constructor(source, target) {
    this.source = source;   // 节点对象
    this.target = target;
    this.subdivisionPoints = [];  // 包含 source 和 target 之间的插值点
    this.compatibilityList = [];  // 后续填充兼容边
  }

  // 初始化 subdivisionPoints，为中点
  initializeSubdivisionPoints(P) {
    this.subdivisionPoints = [];
    for (let i = 0; i <= P + 1; i++) {
      const t = i / (P + 1);
      this.subdivisionPoints.push(interpolate(this.source, this.target, t));
    }
  }

  refineSubdivisionPoints() {
    const newPoints = [this.subdivisionPoints[0]];

    for (let i = 0; i < this.subdivisionPoints.length - 1; i++) {
      const p = this.subdivisionPoints[i];
      const q = this.subdivisionPoints[i + 1];
      const mid = interpolate(p, q, 0.5);
      newPoints.push(mid);
      newPoints.push(q);
    }

    this.subdivisionPoints = newPoints;
  }
}

// 构建Edge对象列表
export function buildEdges(rawEdges, rawNodes, P) {
  const nodesMap = new Map(rawNodes.map(n => [n.id, n]));

  const edges = [];

  for (const e of rawEdges) {
    const source = nodesMap.get(e[0]);
    const target = nodesMap.get(e[1]);

    if (!source || !target) continue;

    const edge = new Edge(source, target);
    edge.initializeSubdivisionPoints(P);
    edges.push(edge);
  }

  return edges;
}


function dotProduct(v1, v2) {
  return v1.x * v2.x + v1.y * v2.y;
}

function vector(p1, p2) {
  return { x: p2.lon - p1.lon, y: p2.lat - p1.lat };
}

function magnitude(v) {
  return Math.sqrt(v.x * v.x + v.y * v.y);
}

function normalize(v) {
  const mag = magnitude(v);
  return { x: v.x / mag, y: v.y / mag };
}

function midpoint(p1, p2) {
  return {
    lon: (p1.lon + p2.lon) / 2,
    lat: (p1.lat + p2.lat) / 2,
  };
}

function distance(p1, p2) {
  const dx = p1.lon - p2.lon;
  const dy = p1.lat - p2.lat;
  return Math.sqrt(dx * dx + dy * dy);
}


function angleCompatibility(e1, e2) {
  const v1 = vector(e1.source, e1.target);
  const v2 = vector(e2.source, e2.target);
  return Math.abs(dotProduct(normalize(v1), normalize(v2)));
}


function scaleCompatibility(e1, e2) {
  const l1 = distance(e1.source, e1.target);
  const l2 = distance(e2.source, e2.target);
  return 2.0 / (l1 / l2 + l2 / l1);  // 比值越接近，值越接近1
}

function positionCompatibility(e1, e2) {
  const m1 = midpoint(e1.source, e1.target);
  const m2 = midpoint(e2.source, e2.target);
  const l1 = distance(e1.source, e1.target);
  const l2 = distance(e2.source, e2.target);
  return 2.0 / (distance(m1, m2) / Math.min(l1, l2) + Math.min(l1, l2) / distance(m1, m2));
}


function visibilityCompatibility(e1, e2) {
  const I0 = projectPointOnEdge(midpoint(e2.source, e2.target), e1);
  const I1 = projectPointOnEdge(midpoint(e1.source, e1.target), e2);

  const mid1 = midpoint(e1.source, e1.target);
  const mid2 = midpoint(e2.source, e2.target);

  return Math.max(0, 1 - (distance(I0, mid1) + distance(I1, mid2)) / distance(mid1, mid2));
}

function projectPointOnEdge(p, edge) {
  const a = edge.source;
  const b = edge.target;
  const ab = vector(a, b);
  const ap = vector(a, p);
  const t = dotProduct(ap, ab) / dotProduct(ab, ab);
  const clampedT = Math.max(0, Math.min(1, t));
  return interpolate(a, b, clampedT);
}


export function calculateCompatibility(e1, e2) {
  return (
    angleCompatibility(e1, e2) *
    scaleCompatibility(e1, e2) *
    positionCompatibility(e1, e2) *
    visibilityCompatibility(e1, e2)
  );
}

export function buildCompatibilityLists(edges, threshold = 0.6) {
  for (let i = 0; i < edges.length; i++) {
    for (let j = i + 1; j < edges.length; j++) {
      const compatibility = calculateCompatibility(edges[i], edges[j]);
      if (compatibility > threshold) {
        edges[i].compatibilityList.push(edges[j]);
        edges[j].compatibilityList.push(edges[i]);
      }
    }
  }
}


export function applyEdgeForces(edges, stepSize) {
  for (const edge of edges) {
    const points = edge.subdivisionPoints;
    const forces = Array(points.length).fill().map(() => ({ x: 0, y: 0 }));

    for (const compatibleEdge of edge.compatibilityList) {
      const compatPoints = compatibleEdge.subdivisionPoints;

      for (let i = 1; i < points.length - 1; i++) {
        const pi = points[i];
        const qi = compatPoints[i];

        // 使用 lon/lat 计算吸引力向量
        const fx = qi.lon - pi.lon;
        const fy = qi.lat - pi.lat;

        forces[i].x += fx;
        forces[i].y += fy;
      }
    }

    // 更新 subdivision points 位置（施加合力）
    for (let i = 1; i < points.length - 1; i++) {
      points[i].lon += forces[i].x * stepSize;
      points[i].lat += forces[i].y * stepSize;
    }
  }
}


export function runFDEB(edges, options) {
  // 逐阶段执行
  let currentStepSize = options.S;

  for (let phase = 0; phase < options.K; phase++) {
    for (let iter = 0; iter < options.C; iter++) {
      applyEdgeForces(edges, currentStepSize);
    }

    // 除了最后一轮，都进行 subdivision 点数翻倍
    if (phase < options.K - 1) {
      for (const edge of edges) {
        // edge.subdivisionPoints = interpolate(edge.source, edge.target, currentP);
        edge.refineSubdivisionPoints();
      }

      currentStepSize *= 0.5; // 冷却
    }
  }
}

